This invention relates to ciphering systems, methods and computer program products, and more particularly to systems, methods and computer program products for reducing effective key length of ciphers.
Symmetric-key ciphers are widely used for encryption in both commercial and government applications to protect the privacy and integrity of a wide variety of information. The strength of a symmetric-key cipher is generally tied to its key length. Typically, as the number of independent key bits increases the cipher becomes stronger.
There are many symmetric-key block ciphers with different key lengths which can offer different levels of security, flexibility, and efficiency. These include DES, RC5, CAST, Blowfish, FEAL, SAFER, and IDEA. For example, DES uses a 56-bit key to encrypt a 64-bit input plaintext to produce a 64-bit output ciphertext. These ciphers are described for example, in Rivest, xe2x80x9cThe RC5 Encryption Algorithmxe2x80x9d, Dr. Dobb""s Journal, Vol. 20, No. 1, January 1995, pp. 146-148; Schneier, xe2x80x9cThe Blowfish Encryption Algorithmxe2x80x9d, Dr. Dobb""s Journal, Vol. 19, No. 4, April 1994, Pages 38-40; National Bureau of Standards, xe2x80x9cData Encryption Standardxe2x80x9d, FIPS PUB 46, January 1977; Massey, xe2x80x9cSAFER K-64: A Byte-Oriented Block-Ciphering Algorithmxe2x80x9d, Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 1-17; Adams, xe2x80x9cConstructing Symmetric Ciphers Using the CAST Design Procedurexe2x80x9d, Design, Codes, and Cryptography, Vol. 12, No. 3, November 1997, pp. 283-316; and Schneier, xe2x80x9cThe IDEA Encryption Algorithmxe2x80x9d, Dr. Dobb""s Journal, Vol. 18, No. 13, December 1993, pp. 50-56. The disclosures of all these publications are hereby incorporated herein by reference.
When used in commercial applications, data encryption is often subject to government regulations limiting the use, import and/or export of equipment supporting data privacy to certain key lengths. For example, under the United States Department of Commerce regulations, when the keys are limited to 40 bits, products supporting data encryption are generally exportable. Also, when work on key recovery is undertaken, export of DES with 56-bit key is generally allowed. Therefore, depending on the type of application or regulations, the key size may need to be varied.
Unfortunately, many ciphers are not designed to support variable key length. Moreover, even if a cipher supports variable key length, it is often desirable to reduce the xe2x80x9ceffective key lengthxe2x80x9d (i.e., the number of independent key bits) rather than the actual key length in order to be able to use the same key management and key exchange protocols independent of the application or regulations. The effective key length of a cipher can be reduced by reducing the number of independent key bits in the key. This process is also referred to as xe2x80x9ckey shorteningxe2x80x9d.
Key shortening generates a xe2x80x9cshortened keyxe2x80x9d form an initial (xe2x80x9clongxe2x80x9d) key. Thus, key shortening reduces the effective key length of the initial key without affecting its actual length. For example, denote the initial and shortened keys by K and Kxe2x80x2, respectively. Let l be the actual length of K (or Kxe2x80x2) in bits and let r be the number of bits by which K has to be shortened. Thus, the effective length of Kxe2x80x2 is lxe2x88x92r bits.
One technique to derive Kxe2x80x2 from K is to set r specific bits of K to some publicly known constant values. For example, the r left-most bits of K can be set to zero. Unfortunately, Kxe2x80x2 becomes weaker than K by r bits since r bits of Kxe2x80x2 are constant values which are known to the public. Thus, this key shortening technique which fixes some of the key bits to some publicly known constant values, is potentially susceptible to xe2x80x9cshort-cutxe2x80x9d attacks. That is, the work factor required to break the shortened key Kxe2x80x2 may be less than 2lxe2x88x92r, due to the way some ciphers work.
For example, DES includes 16 rounds of identical operations in which the data is mixed with the key. For each round, a key transformation algorithm derives a sub-key from the initial 56-bit key. In each round, a sub-key is mixed with the data. The way the DES key transformation algorithm works, it preserves the initial key bits. Thus, if some of the initial key bits are fixed, then these fixed bits will propagate into the sub-keys, reducing the entropy of the sub-keys. That is, some of the bits in the sub-keys will have known values. This may lead to short-cut attacks. To avoid such a problem, a key shortening scheme preferably should produce a shortened key from an initial key that is pseudo-random with no fixed bits.
Another potential issue with such a key shortening scheme is that exposure of the shortened key Kxe2x80x2 may reveal information about the initial key K. That is, if Kxe2x80x2 is exposed, an exhaustive search for K may take only 2r trials. This can be a problem since in some applications, it might be desirable to use both the keys for two different sessions, one for a xe2x80x9cstrong sessionxe2x80x9d and one for a xe2x80x9cweak sessionxe2x80x9d.
The Commercial Data Masking Facility (CDMF) key shortening scheme can avoid these issues. CDMF is described in U.S. Pat. No. 5,323,464 to Elander et al., entitled xe2x80x9cCommercial Data Maskingxe2x80x9d, assigned to the assignee of the present invention, the disclosure of which is incorporated by reference herein in its entirety. CDMF is also described in Johnson et al., xe2x80x9cThe Commercial Data Masking facility (CDMF) Data Privacy Algorithmxe2x80x9d, IBM Journal of Research and Development, Vol. 38, No. 2, March 1994, pp. 217-226; and Johnson et al., xe2x80x9cDesign of the Commercial Data Masking Facility Data Privacy Algorithmxe2x80x9d, 1st ACM Conference on Computer and Communications Security, ACM Press, 1993, pp. 93-96, the disclosures of which are incorporated by reference herein in their entirety. CDMF generates a pseudo-random 40-bit DES key with no fixed bits from a 56-bit key. Given a 64-bit DES key (including the 8 parity bits), the CDMF derives a 40-bit key using the following steps:
1. Set the parity bits (i.e., bits 8, 16, 24, 32, 40, 48, 56, and 64) in the key to 0.
2. Encrypt the output of Step 1 using DES and the key 0Xc408b0540ba1e0ae.
3. EXCLUSIVE-OR (XOR) the results of Steps 1 and 2.
4. Zero the parity bits (i.e., bits 8, 16, 24, 32, 40, 48, 56, and 64) and the following 16 bits in the output of Step 3: bits 1, 2, 3, 4, 17, 18, 19, 20, 33, 34, 35, 36, 49, 50, 51, and 52.
5. Encrypt the output of Step 4 using DES and the key 0Xef2c041ce6382fe6.
6. Set the parity bits (i.e., bits 8, 16, 24, 32, 40, 48, 56, and 64) in the result of Step 5 if desired.
The output of step 6 is the CDMF-derived shortened key which is used in a standard DES invocation.
Notwithstanding the improvement of CDMF, there continues to be a need for improved systems, methods and computer program products for reducing effective key length of ciphers. Key length reducing systems, methods and computer program products should preferably be generic in the sense that they can be used with any cipher and any size key, and can generate a shortened key which is of the same length as the initial long key.
The present invention includes systems, methods and/or computer program products that reduce effective key length of a symmetric key cipher by deriving an intermediate value from an initial key, using a one-way cryptographic function. Predetermined bit locations of the intermediate value are selected to obtain an intermediate key. An intermediate shortened key is derived from the intermediate key by setting predetermined bit locations of the intermediate key to predetermined values. A diffused intermediate shortened key is derived from the intermediate shortened key using the one-way cryptographic function. Predetermined bit locations of the diffused intermediate shortened key are then selected to obtain a shortened key.
Systems, methods and/or computer program products for reducing effective key length of a symmetric key cipher according to the invention can be used with any cipher and any size key, and can generate a shortened key which is of the same length as the initial (long) key. These systems, methods and/or computer program products can be cryptographically strong, and can produce shortened keys that may not be susceptible to short-cut attacks. Additionally, exposure of the shortened key need not reveal any information about the initial key. Modifications to existing key management systems need not be made, and preestablished and dynamically established keys may be used. Existing key exchange protocols may be used to distribute long keys which are shortened using systems, methods and/or computer program products according to the present invention.
In first embodiments of the invention, the one-way cryptographic function is a one-way hash function. An intermediate value is derived from an initial key by concatenating one-way hashes of the initial key and a predetermined number of increments of the initial key. A diffused intermediate shortened key is derived from the intermediate shortened key by concatenating one-way hashes of the diffused intermediate shortened key and a predetermined number of increments of the diffused intermediate shortened key. Thus, a one-way hash function and the initial key are used to derive a shortened key.
Second embodiments of the invention use the symmetric key cipher itself to perform the one-way cryptographic function. The initial key is divided into a plurality of initial key subblocks. In order to derive an intermediate value from the initial key, a predetermined number of EXCLUSIVE-ORs of a function of a preceding initial key subblock, a succeeding initial key subblock and an encryption of the succeeding initial key subblock under the initial key are recursively concatenated. The intermediate shortened key is divided into a plurality of intermediate shortened key subblocks. A diffused intermediate shortened key is derived from the intermediate shortened key by recursively concatenating a predetermined number of EXCLUSIVE-ORs of a function of a preceding intermediate shortened key subblock, succeeding intermediate shortened key subblock and an encryption of the succeeding intermediate shortened key subblock under the intermediate shortened key. Accordingly, the cipher itself and the initial key are used to generate a shortened key.
Systems, methods and/or computer program products according to the invention can therefore derive a shortened key from an initial key by performing at least one-way cryptographic function using the initial key and no other key. The at least one-way cryptographic function can be a one-way hash function and/or a symmetric key cipher, that use the initial key and no other key. Improved systems, methods and/or computer program products for reducing effective key length of ciphers may thereby be provided.